package chapter04_RecursionAndDynamic.minCoins;

import com.sun.org.apache.xml.internal.security.algorithms.implementations.IntegrityHmac;

/**
 * 描述：
 *      最少的找钱数
 *      给定一个arr数组，数组中的值代表货币面值的大小，给定一个aim，求找钱数为aim的用的最少的货币数，
 *      arr中都是正数，且货币使用一次
 * @author hl
 * @date 2021/6/5 8:41
 */
public class MinCoins2 {
    public static void main(String[] args) {
        int[] arr = {5,2,5,3,5};
        int aim = 15;
        int num = minCoins(arr, aim);
        int num2 = minCoins2(arr, aim);
        System.out.println(num);
        System.out.println(num2);
    }
    public static int minCoins(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int sum = 0, n = arr.length;
        for (int i : arr) {
            sum += i;
        }
        if (sum < aim) {
            return -1;
        }
        int[][] dp = new int[n][aim + 1];
        int max = Integer.MAX_VALUE;
        for (int j = 1; j <= aim; j++) {
            dp[0][j] = max;
        }
        if(arr[0] <= aim){
            dp[0][arr[0]] = 1;
        }
        int left = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                left = max;
                if (j >= arr[i] && dp[i - 1][j - arr[i]] != max) {
                    left = dp[i - 1][j - arr[i]] + 1;
                }
                dp[i][j] = Math.min(left, dp[i - 1][j]);
            }
        }
        return dp[n - 1][aim] != max ? dp[n - 1][aim] : -1;
    }

    public static int minCoins2(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int sum = 0, n = arr.length;
        for (int i : arr) {
            sum += i;
        }
        if (sum < aim) {
            return -1;
        }
        int[] dp = new int[aim + 1];
        int max = Integer.MAX_VALUE;
        for (int j = 1; j <= aim; j++) {
            dp[j] = max;
        }
        if(arr[0] <= aim){
            dp[arr[0]] = 1;
        }
        int leftUp = 0;
        for (int i = 1; i < n; i++) {
            for (int j = aim; j > 0; j--) {
                leftUp = max;
                if (j >= arr[i] && dp[j - arr[i]] != max) {
                    leftUp = dp[j - arr[i]] + 1;
                }
                dp[j] = Math.min(leftUp, dp[j]);
            }
        }
        return dp[aim] != max ? dp[aim] : -1;
    }
}
